package main

import (
	"fmt"
	"sync"
	"unsafe"
)

// Set 一般很多编程语言库，会把不可重复集合（Collection）命名为 Set，这个 Set 中文直译为集合，在某些上下文条件下，
// 我们大脑要自动过滤，集合这词指的是不可重复集合还是指统称的集合，在这里都可以看到中文博大精深。
//
// 不可重复集合 Set 存放数据，特点就是没有数据会重复，会去重。你放一个数据进去，再放一个数据进去，如果两个数据一样，那么只会保存一份数据。
//
// 集合 Set 可以没有顺序关系，也可以按值排序，算一种特殊的列表。
//
// 因为我们知道字典的键是不重复的，所以只要我们不考虑字典的值，就可以实现集合，我们来实现存整数的集合 Set：
type Set struct {
	m map[int]struct{}		// 字典实现不可重复集合Set，因为字段key不能重复
	len int 				// 集合的大小
	sync.RWMutex		// 锁，实现并发安全  (这种定义方式叫“匿名字段”)
}

// NewSet 初始化集合
func NewSet(cap int64) *Set {
	// 使用一个容量为 cap 的 map 来实现不可重复集合。map 的值我们不使用，所以值定义为空结构体 struct{}，因为空结构体的内存地址都一,
	// 不占用内存空间
	temp := make(map[int]struct{}, cap)
	return &Set {
		m: temp,
	}
}

// Add 往集合Set中添加一个元素
// 时间复杂度等于字典设置键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为 O(n)
func (s *Set) Add(item int) {
	s.Lock()
	defer s.Unlock()
	s.m[item] = struct{}{}  // 实际往字典中添加这个键
	s.len = len(s.m)
}

// Remove 从集合Set中删除一个元素
// 时间复杂度等于字典删除键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为 O(n)
func (s *Set) Remove(item int) {
	s.Lock()
	defer s.Unlock()

	// 如果集合为空直接返回即可
	if s.len == 0 {
		return
	}

	// 实际上：从字典中删除这个键
	delete(s.m, item)
	s.len = len(s.m)  // 重新计算元素数量
}

// Has 查看元素是否在集合中
// 时间复杂度等于字典获取键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为 O(n)
func (s *Set) Has(item int) bool {
	s.RLock()
	defer s.RUnlock()
	_, ok := s.m[item]  // 如果item在字典中，ok为true，否则为false
	return ok
}

// Len 查看集合大小
func (s *Set) Len() int {
	return s.len
}

// IsEmpty 查看集合是否为空
// 时间复杂度：O(1)
func (s *Set) IsEmpty() bool {
	return s.Len() == 0
}

// Clear 清除集合所有元素
func (s *Set) Clear() {
	s.Lock()
	defer s.Unlock()
	s.m = map[int]struct{}{}  // 字典重新赋值
	s.len = 0  				// 大小归零
}

// List 将集合转化为数组切片
// 时间复杂度：O(n)
func (s *Set) List() []int {
	s.RLock()
	defer s.RUnlock()
	list := make([]int, 0, s.len)
	for item := range s.m {
		list = append(list, item)
	}
	return list
}

// 为什么使用空结构体
func other() {
	a := struct{}{}
	b := struct{}{}
	if a == b {
		fmt.Printf("right:%p\n", &a)
	}
	fmt.Println(unsafe.Sizeof(a))
}

func main() {


	//other()
	// 初始化一个容量为5的不可重复集合
	s := NewSet(5)
	s.Add(1)
	s.Add(1)
	s.Add(2)
	fmt.Println("list of all items", s.List())
	s.Clear()
	if s.IsEmpty() {
		fmt.Println("empty")
	}
	s.Add(1)
	s.Add(2)
	s.Add(3)
	if s.Has(2) {
		fmt.Println("2 does exist")
	}
	s.Remove(2)
	s.Remove(3)
	fmt.Println("list of all items", s.List())
}














